Traditional multitasking operating systems (e.g., UNIX, Windows) have been implemented in computing environments to provide a way to allocate the resources of the computing environment (e.g., CPU, memory, Input/Output (I/O) devices) among various user applications that may be running simultaneously in the computing environment. The operating system itself includes a number of functions (executable code) and data structures that may be used to implement the resource allocation services of the operating system. A program that performs actions may be referred to as a task (also known as a “thread”), and a collection of tasks may be referred to as a “process”. Upon loading and execution of the operating system into the computing environment, “system tasks” and “system processes” are created in order to support the resource allocation needs of the system. User applications likewise, upon execution, may cause the creation of tasks (“user tasks”) and processes (“user processes”) in order to perform the actions desired from the application.
Resources may be allocated to a task “statically” at a task's creation, for the entire duration of the task's existence. Alternatively, resources may be allocated to a task “dynamically”, when requested by the task. Memory may be allocated to tasks as “memory objects”, which may be contiguous blocks of memory, identified by a pointer or reference. Memory objects may, but need not, correspond to so-called “objects” in an object-oriented programming language like C++ and Java. Allocated memory objects may include special fields or locations that store information about the memory object and the memory object's use in the system, e.g., a field containing information for use by a resource reclamation procedure, pointers to class information in an object-oriented programming system, or synchronization information.
When a portion of memory is no longer used by any task, a “garbage collector” may be used to reclaim the unused memory so that the memory can be re-allocated to other tasks. The garbage collector may run as a separate task or process, e.g., cooperating with a separate memory allocation task or function. For example, in a Java Virtual Machine, a conventional application, memory allocation may be provided directly to tasks by a library function call, while a garbage collector runs as a separate task. Skilled practitioners will recognize that other ways of implementing a garbage collector procedure are possible, e.g., as part of the operating system, or as part of a task or process that also handles memory allocation.
In most conventional implementations, when the garbage collector needs to run, all other tasks may be suspended so that the garbage collector can run uninterrupted. However, suspending all processes for garbage collection may be unsuitable in real time systems, i.e., systems where performance of particular tasks or processes must be guaranteed to complete in a fixed time interval.
Some conventional systems implement so-called “concurrent” garbage collection. In concurrent garbage collection, a task performing garbage collection and other tasks that may access the memory may run concurrently. Systems with concurrent garbage collection may have better real-time performance for user tasks than systems that suspend all user tasks during garbage collection. However, a problem with concurrent garbage collection is dealing with any changes made to the memory by tasks running concurrently with the garbage collection procedure.
The problem of concurrent changes is illustrated in FIG. 1 and FIG. 2. In FIG. 1, object A contains a pointer to object B. Suppose a garbage collector has already completed its processing of object C, and has visited object A but not looked at A's ‘children’, i.e., objects referenced by pointers contained in object A, e.g., object B. Between the time the garbage collector first visits object A, and the time the garbage collector visits A's child B, another concurrently executing task may copy the pointer from object A into object C, and put some other value in object A, deleting the pointer to object B. The result is shown in FIG. 2. Now the garbage collector may never find object B, and may reach the conclusion that object B is no longer referenced and therefore is “garbage”, i.e., memory to be reclaimed. In this example, however, object B is still in use by object C and thus should not be reclaimed.
Previous systems implementing concurrent garbage collection systems have relied on hardware memory management techniques to prevent mutual exclusion violations that interfere with garbage collection. For example, special bits in memory may be set so that a hardware memory management unit creates a so-called “read barrier”. The memory management unit traps attempts to read from locations protected by the read barrier. In the example above, the attempt to copy the pointer from A may be trapped if all of A's children have not yet been scanned. The trap may generate an interrupt which invokes special code to be executed. Code invoked by the interrupt may update the information that is used by the garbage collection procedure related to the location protected by the read barrier. Alternatively, special bits in memory may be set so that a hardware memory management unit creates a so-called “write barrier”, which traps attempts to write to protected locations. In the example above, the attempt to write to the pointer in location A before all of A's children have been scanned may be trapped by the write barrier, producing an interrupt, and allowing interrupt drive code to take action to maintain the correctness of the garbage collection procedure.
However, small low-cost microprocessors may not have hardware memory management available. Even in larger microprocessors with hardware memory management, hardware memory management may suffer from unreliable real-time response, precluding its use in real-time systems.